/**
 * 空间网格分区器
 * 
 * 将游戏世界分成均匀的网格，用于快速查询区域内的实体
 * 
 * 性能：
 * - 添加实体：O(1)
 * - 查询区域：O(1) 到 O(k)，k 是区域内的实体数量
 * 
 * @author AI Assistant
 * @date 2025-11-26
 */

import { ecs } from "../../../core/ecs/ECS";

/**
 * 空间网格分区器
 */
export class SpatialGrid {
    /** 网格大小（像素） */
    private cellSize: number;
    
    /** 网格数据：key = "gridX,gridY", value = 实体数组 */
    private grid: Map<string, ecs.Entity[]>;
    
    /**
     * 构造函数
     * @param cellSize 网格大小（像素），建议值：100-200
     */
    constructor(cellSize: number = 100) {
        this.cellSize = cellSize;
        this.grid = new Map();
    }
    
    /**
     * 获取实体所在的网格坐标
     */
    private getGridKey(x: number, y: number): string {
        const gridX = Math.floor(x / this.cellSize);
        const gridY = Math.floor(y / this.cellSize);
        return `${gridX},${gridY}`;
    }
    
    /**
     * 添加实体到网格
     * @param entity 实体
     * @param x X 坐标
     * @param y Y 坐标
     */
    addEntity(entity: ecs.Entity, x: number, y: number): void {
        const key = this.getGridKey(x, y);
        
        if (!this.grid.has(key)) {
            this.grid.set(key, []);
        }
        
        const cell = this.grid.get(key)!;
        
        // 避免重复添加
        if (!cell.includes(entity)) {
            cell.push(entity);
        }
    }
    
    /**
     * 从网格移除实体
     */
    removeEntity(entity: ecs.Entity, x: number, y: number): void {
        const key = this.getGridKey(x, y);
        const cell = this.grid.get(key);
        
        if (cell) {
            const index = cell.indexOf(entity);
            if (index !== -1) {
                cell.splice(index, 1);
            }
        }
    }
    
    /**
     * 更新实体位置（从旧位置移除，添加到新位置）
     */
    updateEntity(entity: ecs.Entity, oldX: number, oldY: number, newX: number, newY: number): void {
        const oldKey = this.getGridKey(oldX, oldY);
        const newKey = this.getGridKey(newX, newY);
        
        // 如果网格没变，不需要更新
        if (oldKey === newKey) {
            return;
        }
        
        // 从旧网格移除
        const oldCell = this.grid.get(oldKey);
        if (oldCell) {
            const index = oldCell.indexOf(entity);
            if (index !== -1) {
                oldCell.splice(index, 1);
            }
        }
        
        // 添加到新网格
        this.addEntity(entity, newX, newY);
    }
    
    /**
     * 获取指定区域内的实体
     * @param x 中心 X 坐标
     * @param y 中心 Y 坐标
     * @param radius 半径
     * @returns 区域内的实体数组
     */
    getEntitiesInArea(x: number, y: number, radius: number): ecs.Entity[] {
        const entities: ecs.Entity[] = [];
        const seen = new Set<ecs.Entity>(); // 避免重复
        
        // 计算需要检查的网格范围
        const minX = Math.floor((x - radius) / this.cellSize);
        const maxX = Math.floor((x + radius) / this.cellSize);
        const minY = Math.floor((y - radius) / this.cellSize);
        const maxY = Math.floor((y + radius) / this.cellSize);
        
        // 遍历相关网格
        for (let gx = minX; gx <= maxX; gx++) {
            for (let gy = minY; gy <= maxY; gy++) {
                const key = `${gx},${gy}`;
                const cell = this.grid.get(key);
                
                if (cell) {
                    for (const entity of cell) {
                        // 避免重复添加
                        if (!seen.has(entity)) {
                            seen.add(entity);
                            entities.push(entity);
                        }
                    }
                }
            }
        }
        
        return entities;
    }
    
    /**
     * 获取指定网格内的实体
     */
    getEntitiesInCell(gridX: number, gridY: number): ecs.Entity[] {
        const key = `${gridX},${gridY}`;
        return this.grid.get(key) || [];
    }
    
    /**
     * 清空网格
     */
    clear(): void {
        this.grid.clear();
    }
    
    /**
     * 获取统计信息
     */
    getStats(): {
        totalCells: number;
        totalEntities: number;
        averageEntitiesPerCell: number;
        maxEntitiesInCell: number;
    } {
        let totalEntities = 0;
        let maxEntitiesInCell = 0;
        
        for (const cell of this.grid.values()) {
            totalEntities += cell.length;
            maxEntitiesInCell = Math.max(maxEntitiesInCell, cell.length);
        }
        
        return {
            totalCells: this.grid.size,
            totalEntities,
            averageEntitiesPerCell: this.grid.size > 0 ? totalEntities / this.grid.size : 0,
            maxEntitiesInCell
        };
    }
}

